public class FindPaths {

    public static void main(String[] args) {
        System.out.println(new FindPaths().findPaths(36,5,50,15,3));
    }

    long ans = 0;
    boolean[][] flag;
    int[][] temp = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    public int findPaths1(int m, int n, int maxMove, int startRow, int startColumn) {
        flag = new boolean[m][n];
        dfs(startRow, startColumn, 0, maxMove, m, n);
        return (int) (ans % (Math.pow(10, 9) + 7));
    }

    public void dfs(int i, int j, int step, int maxMove, int m, int n) {
        if (i < 0 || i >= m || j < 0 || j >= n) {
            ++ans;
            return;
        }
        if (step == maxMove) return;
        flag[i][j] = true;
        for (int[] ints : temp) {
            dfs(i + ints[0], j + ints[1], step + 1, maxMove, m, n);
        }
        flag[i][j] = false;
    }

    public int findPaths2(int m, int n, int maxMove, int startRow, int startColumn) {
        if (maxMove == 0) return 0;
        final int MOD = 1000000007;
        int ans;
        int[][][] dp = new int[maxMove + 1][m][n];
        int[][] temp = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int[] ints : temp) {
                    if (i + ints[0] >= m || i + ints[0] < 0 || j + ints[1] >= n || j + ints[1] < 0) dp[1][i][j]++;
                }
            }
        }
        ans = dp[1][startRow][startColumn];
        for (int i = 2; i <= maxMove; i++) {
            for (int j = 0; j < m; j++) {
                for (int k = 0; k < n; k++) {
                    for (int[] ints : temp) {
                        int x = j + ints[0];
                        int y = k + ints[1];
                        if (x >= 0 && x < m && y >= 0 && y < n) dp[i][j][k] = (dp[i][j][k] + dp[i - 1][x][y]) % MOD;
                    }
                    if (j == startRow && k == startColumn) ans = (dp[i][j][k] + ans) % MOD;
                }
            }
        }
        return ans;
    }

    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        if (maxMove == 0) return 0;
        final int MOD = 1000000007;
        int[][][] dp = new int[maxMove + 1][m][n];
        int[][] temp = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        for (int i = 1; i <= maxMove; i++) {
            for (int j = 0; j < m; j++) {
                for (int k = 0; k < n; k++) {
                    if (j == 0) dp[i][j][k]++;
                    if (j == m - 1) dp[i][j][k]++;
                    if (k == 0) dp[i][j][k]++;
                    if (k == n - 1) dp[i][j][k]++;
                    for (int[] ints : temp) {
                        int x = j + ints[0];
                        int y = k + ints[1];
                        if (x >= 0 && x < m && y >= 0 && y < n)
                            dp[i][j][k] = (dp[i][j][k] + dp[i - 1][x][y]) % MOD;
                    }
                }
            }
        }
        return dp[maxMove][startRow][startColumn];
    }
}
